#[derive(Debug, Clone)]
pub struct Node {
    pub left: usize,
    pub right: usize,
    pub up: usize,
    pub down: usize,
    pub column: usize,
    pub row: usize,
}

pub struct DLX {
    pub nodes: Vec<Node>,
    pub columns: Vec<usize>,
    pub solution: Vec<usize>,
}

impl DLX {
    pub fn new(rows: usize, cols: usize) -> Self {
        let mut nodes = Vec::with_capacity(rows * cols + cols + 1);
        let mut columns = vec![0; cols + 1];
        
        // Initialize column headers
        for i in 0..=cols {
            nodes.push(Node {
                left: if i == 0 { cols } else { i - 1 },
                right: if i == cols { 0 } else { i + 1 },
                up: i,
                down: i,
                column: i,
                row: 0,
            });
            columns[i] = 0;
        }
        
        DLX {
            nodes,
            columns,
            solution: Vec::new(),
        }
    }
    
    pub fn add_row(&mut self, row: usize, cols: &[usize]) {
        let first = self.nodes.len();
        
        for &col in cols {
            let col_header = col;
            let new_node_idx = self.nodes.len();
            
            // Update column size
            self.columns[col_header] += 1;
            
            // Create new node
            let new_node = Node {
                left: new_node_idx - 1,
                right: new_node_idx + 1,
                up: self.nodes[col_header].up,
                down: col_header,
                column: col_header,
                row,
            };
            
            // Link neighbors
            self.nodes[new_node.up].down = new_node_idx;
            self.nodes[col_header].up = new_node_idx;
            
            self.nodes.push(new_node);
        }
        
        // Fix first and last node's left/right pointers
        let last = self.nodes.len() - 1;
        self.nodes[first].left = last;
        self.nodes[last].right = first;
    }
    
    pub fn cover(&mut self, col: usize) {
        // Remove column header
        {
            let left = self.nodes[col].left;
            let right = self.nodes[col].right;
            self.nodes[left].right = right;
            self.nodes[right].left = left;
        }
        
        // Remove all rows in this column
        let mut i = self.nodes[col].down;
        while i != col {
            let mut j = self.nodes[i].right;
            while j != i {
                let up = self.nodes[j].up;
                let down = self.nodes[j].down;
                self.nodes[down].up = up;
                self.nodes[up].down = down;
                self.columns[self.nodes[j].column] -= 1;
                j = self.nodes[j].right;
            }
            i = self.nodes[i].down;
        }
    }
    
    pub fn uncover(&mut self, col: usize) {
        // Restore all rows in this column
        let mut i = self.nodes[col].up;
        while i != col {
            let mut j = self.nodes[i].left;
            while j != i {
                let column = self.nodes[j].column;
                let up = self.nodes[j].up;
                let down = self.nodes[j].down;
                self.columns[column] += 1;
                self.nodes[down].up = j;
                self.nodes[up].down = j;
                j = self.nodes[j].left;
            }
            i = self.nodes[i].up;
        }
        
        // Restore column header
        let left = self.nodes[col].left;
        let right = self.nodes[col].right;
        self.nodes[right].left = col;
        self.nodes[left].right = col;
    }
    
    pub fn solve(&mut self) -> bool {
        if self.nodes[0].right == 0 {
            return true;
        }
        
        // Select column with minimum size
        let mut col = self.nodes[0].right;
        let mut min_size = self.columns[col];
        
        let mut j = self.nodes[col].right;
        while j != 0 {
            if self.columns[j] < min_size {
                col = j;
                min_size = self.columns[j];
            }
            j = self.nodes[j].right;
        }
        
        self.cover(col);
        
        let mut row = self.nodes[col].down;
        while row != col {
            self.solution.push(self.nodes[row].row);
            
            // Cover all columns in this row
            let mut j = self.nodes[row].right;
            while j != row {
                self.cover(self.nodes[j].column);
                j = self.nodes[j].right;
            }
            
            if self.solve() {
                return true;
            }
            
            // Backtrack
            self.solution.pop();
            
            // Uncover all columns in this row
            j = self.nodes[row].left;
            while j != row {
                self.uncover(self.nodes[j].column);
                j = self.nodes[j].left;
            }
            
            row = self.nodes[row].down;
        }
        
        self.uncover(col);
        false
    }
}